We established that the difference between an efficient $O(\log_2(n))$ solution and a slow $O(n^2)$ solution is immense at scale; the key to achieving that optimal time complexity is how the input data is organized.
- A Data Structure (DS) is a specialized format for organizing, processing, retrieving, and storing data.
- It dictates which operations are fast (efficient) and which are slow (inefficient).
- The choice of Data Structure is the single biggest factor in determining the performance characteristics of an algorithm operating on an input size n.
- We analyze data structures based on the cost of their core operations: Search, Insertion, Deletion, and Access.
- For example, the basic Array structure provides $O(1)$ constant time access by index.
- However, an Array requires $O(n)$ linear time for searching for a value without knowing its location (in the worst case).
Array: Core Operation Costs
| Operation | Description | Complexity |
|---|---|---|
| Access (by index) | Retrieving `A[i]` given index `i`. | $O(1)$ |
| Search (worst-case) | Finding a value `t` in an unsorted array. | $O(n)$ |
| Insertion (beginning) | Adding an element at `A[0]`. | $O(n)$ |
| Insertion (end) | Adding an element after the last item. | $O(1)$ |